package BackTracking;//给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的
//句子。 
//
// 说明： 
//
// 
// 分隔时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入:
//s = "catsanddog"
//wordDict = ["cat", "cats", "and", "sand", "dog"]
//输出:
//[
//  "cats and dog",
//  "cat sand dog"
//]
// 
//
// 示例 2： 
//
// 输入:
//s = "pineapplepenapple"
//wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
//输出:
//[
//  "pine apple pen apple",
//  "pineapple pen apple",
//  "pine applepen apple"
//]
//解释: 注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入:
//s = "catsandog"
//wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出:
//[]
// 
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 回溯 👍 533 👎 0


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List<String> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        /**
        * 回溯
        * */
        int len = s.length();
        backTrack(s,wordDict,0,len);
        return res;

    }

    void backTrack(String s, List<String> wordDict, int start, int len){
        if(len<0){
            return;
        }
        if(len==0){
            StringBuffer sb = new StringBuffer();
            for (String s1 : path) {
                sb.append(s1);
            }
            if(s.equals(sb.toString())){
                for (String s1 : path) {
                    sb.append(s1+" ");
                }
                sb.deleteCharAt(sb.length());
                res.add(sb.toString());
            }
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String substring = s.substring(start,i+1);
            boolean contains = wordDict.contains(substring);
            if(contains){
                path.add(substring);
                len -= substring.length();
                backTrack(s, wordDict, i+1, len);
                len += substring.length();
                path.remove(path.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "catsandog";
        List<String> wordDict = Arrays.asList("cats", "dog", "sand", "and", "cat");
        System.out.println(solution.wordBreak(s,wordDict));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
